#include <NTL/ZZ.h>
#include <vector>

NTL::ZZ ex_gcd(NTL::ZZ a, NTL::ZZ b, NTL::ZZ &x, NTL::ZZ &y) // exgcd
{
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  NTL::ZZ r = ex_gcd(b, a % b, x, y);
  NTL::ZZ t = x;
  x = y;
  y = t - a / b * y;
  return r;
}

NTL::ZZ PowMod(NTL::ZZ a, NTL::ZZ n, NTL::ZZ mod) {
  NTL::ZZ ret(1);
  while (n > 0) {
    if (n % 2 == 1)
      ret = (ret * a) % mod;
    a = (a * a) % mod;
    n >>= 1;
  }
  return ret % mod;
}

NTL::ZZ mod_reverse(NTL::ZZ a, NTL::ZZ n) // ax=1(mod n)
{
  NTL::ZZ d, x, y;
  d = ex_gcd(a, n, x, y);
  return (x % n + n) % n;
}

NTL::ZZ FermatInv(NTL::ZZ a, NTL::ZZ b) { return PowMod(a, b - 2, b); }
typedef struct CH_Remainder {
  NTL::ZZ result, mod_num;
} CH_Remainder;

// NTL::ZZ Ch_remainder_theorem(ch_remainder a) // CRT
// {
//   NTL::ZZ k(a[0].mod_num), b(0), z(0);
//   for (int i = 1; a[i].mod_num; i++) {
//     k *= a[i].mod_num;
//   }
//   for (int i = 0; a[i].mod_num; i++) {
//     z = mod_reverse(k / NTL::conv<NTL::ZZ>(a[i].mod_num),
//                     NTL::conv<NTL::ZZ>(a[i].mod_num));
//     b += (NTL::conv<NTL::ZZ>(a[i].result) * (k / a[i].mod_num) * z);
//   }
//   return b % k;
// }

NTL::ZZ Ch_remainder_theorem(CH_Remainder a[], int crt_num) {
  NTL::ZZ M(1), ans(0), x, y;
  NTL::ZZ lcm[crt_num];
  for (int i = 0; i < crt_num; i++)
    M *= a[i].mod_num;
  for (int i = 0; i < crt_num; i++) {
    lcm[i] = M / a[i].mod_num;
    ex_gcd(lcm[i], a[i].mod_num, x, y);
    ans = ((ans + a[i].result * lcm[i] * x) % M + M) % M;
  }
  return ans;
}

void CRT(std::vector<NTL::ZZ> &a, std::vector<NTL::ZZ> &m, NTL::ZZ &x,
         NTL::ZZ &Mod) {
  Mod = 1;
  for (auto &i : m)
    Mod *= i;

  NTL::ZZ d, s, t;
  int size = m.size();
  std::vector<NTL::ZZ> M(size);
  std::vector<NTL::ZZ> M_inv(size);
  for (int i = 0; i < size; i++) {
    M[i] = Mod / m[i];
    NTL::XGCD(d, M_inv[i], t, M[i], m[i]);
  }

  x = 0;
  for (int i = 0; i < size; i++) {
    x += a[i] * M[i] * M_inv[i];
    x %= Mod;
  }
}